package com.wc.算法基础课.C第三讲搜索与图论.Dijkstra.通信线路;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/4/16 8:39
 * @description https://www.acwing.com/problem/content/342/
 */
public class Answer {
    /**
     * 思路：这个付钱相当于只需要付一个线的钱， 超过的免费，小于的不用付，那就有二分的性质了
     */
    static Scanner sc = new Scanner(System.in);
    static int N = 1010, M = 20010;
    static int[] h = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    static int INF = 1000010;
    static int idx = 1;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(o -> o[0]));
    static int n, m, k;

    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        while (m-- > 0) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            add(a, b, c);
            add(b, a, c);
        }
        int l = 0, r = INF;
        while (l < r) {
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        if (r == INF) System.out.println(-1);
        else System.out.println(r);
    }

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }

    static boolean check(int mid) {
        Arrays.fill(dist, 1, n + 1, INF);
        Arrays.fill(st, 1, n + 1, false);
        dist[1] = 0;
        q.add(new int[]{0, 1});
        while (!q.isEmpty()) {
            int t = q.poll()[1];
            if (st[t]) continue;
            st[t] = true;
            for (int i = h[t]; i > 0; i = ne[i]) {
                int j = e[i];
                if (dist[j] > dist[t] + (w[i] > mid ? 1 : 0)) {
                    dist[j] = dist[t] + (w[i] > mid ? 1 : 0);
                    q.add(new int[]{dist[j], j});
                }
            }
        }
        return dist[n] <= k;
    }
}


